//请判断一个链表是否为回文链表。 
//
// 示例 1: 
//
// 输入: 1->2
//输出: false 
//
// 示例 2: 
//
// 输入: 1->2->2->1
//输出: true
// 
//
// 进阶： 
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 链表 双指针 
// 👍 1011 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;
public class PalindromeLinkedList {
    public static void main(String[] args) {
        Solution solution = new PalindromeLinkedList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 找中点
    // 截一半，翻转
    // 双指针遍历并比较
    public boolean isPalindrome(ListNode head) {
        if (head==null){return true;}

        int count = 0;
        ListNode cur = head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        ListNode slow = head;
        ListNode fast = head;
        if (count%2==0){
            while (fast!=null && fast.next!=null){
                slow=slow.next;
                fast = fast.next.next;
            }
            ListNode reverse = reverse(slow, null);
            while (reverse!=null){
                if (reverse.val!=head.val){
                    return false;
                }
                reverse=reverse.next;
                head=head.next;
            }
            return true;
        }
        else {
            while (fast!=null && fast.next!=null){
                slow=slow.next;
                fast = fast.next.next;
            }
            ListNode reverse = reverse(slow.next, null);
            while (reverse!=null){
                if (reverse.val!=head.val){
                    return false;
                }
                reverse=reverse.next;
                head=head.next;
            }
            return true;
        }
    }
    public ListNode reverse(ListNode head,ListNode tail){
        if (head==null){return head;}
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur!=tail){
            temp = cur.next;
            cur.next=pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}